class Solution {
    vector<vector<int>> memo;
    int dfs(int left, int right)
    {
        // 猜到了，返回0
        if(left >= right)
            return 0;
        
        if(memo[left][right] != -1)
            return memo[left][right];
        
        int ret = INT_MAX;
        for(int i = left; i <= right; i++)
            ret = min(max(dfs(left, i - 1), dfs(i + 1, right)) + i, ret);

        memo[left][right] = ret;
        return ret;
    }
public:
    int getMoneyAmount(int n) {
        memo = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
        return dfs(1, n);
    }
};